package com.szh.zx.gaoDingJavaBook.chapter9;

/**
 * 自定义双向链表
 */
public class DoubleLinkList<T> {
	//	定义一个内部类node ，node实例代表链表的节点
	private class Node {
		//		保存节点数据，上个节点的引用，下个节点的引用
		private T data;
		private Node prev;
		private Node next;

		public Node() {
		}

		public Node(T date, Node prev, Node next) {
			this.data = date;
			this.prev = prev;
			this.next = next;
		}

	}
//	保存该链表表的头节点
	private Node header;
	private Node tail;
	private int size;
//	创建空链表
	public DoubleLinkList(){
//		空链表
		header = null;
		tail = null;
	}
//	以指定数据元素来创建链表，该链表只有一个元素
	public DoubleLinkList(T element){
		header = new Node(element,null,null);
//		只有一个节点，header ，tail都指向该节点
		tail = header;
		size++;
	}
//	返回链表的长度
	public int lengrth(){
		return size;
	}
//	获取链式线性表中索引index处的元组
	public T get(int index){
		return getNodeByIndex(index).data;
	}
//	根据索引index 获取指定位置的节点
	private Node getNodeByIndex(int index){
		if (index<0||index>size-1){
			throw new IndexOutOfBoundsException("自定义双向链表线性表索引越界");
		}
		if (index<=size/2){
//			从header节点开始
			Node current = header;
			for (int i = 0; i <size/2 && current !=null ; i++,current = current.next) {
				if (i==index){
					return current;
				}
			}
		}else {
//			从tail 节点开始索索
			Node current =tail;
			for (int i = size-1; i >size/2 && current!=null; i++,current=current.prev) {
				if (i==index){
					return current;
				}
			}
		}
		return null;
	}
//	查找链式线性表中指定元素的索引
	public int locate(T element){
//		从头结点开始搜索
		Node current = header;
		for (int i = 0; i < size &&current!=null; i++,current=current.next) {
			if (current.data.equals(element)){
				return i;
			}
		}
		return -1;
	}

//	向线性表的指定位置插入一个元素
	public void insert(T element, int index){
		if (index<0 || index>size){
			throw new IndexOutOfBoundsException("自定义双向链表插入时索引越界");
		}
//		如果还是空链表
		if (header == null){
			add(element);
		}
		else {
//			当index为0时，也就是在链表头插入的是
			if (index==0){
				addAtHeader(element);
			}else {
//				获取插入点前一个节点
				Node prev = getNodeByIndex(index-1);
//				获取插入点的节点
				Node next= prev.next;
//				让新节点的next引用指向next节点，prev指向prev节点
				Node newNode = new Node(element,prev,next);
//				让prev的next指向新节点
				prev.next =newNode;
//				让prev的下一个节点的prev指向新节点
				next.prev = newNode;
				size++;
			}
		}
	}
//	采用尾插法为链表添加新节点
	public void add(T element){
//		如果该链表还是空链表
		if (header == null){
			header = new Node(element,null,null);
//			只有一个节点，header，tail都指向该节点
			tail = header;

		}else {
//			创建新节点，新节点的pre指向tail节点
			Node newNode = new Node(element,tail,null);
//			让尾结点的next指向新增节点
			tail.next = newNode;
//			以新节点作为新的尾结点
			tail = newNode;
		}
		size++;
	}
//	采用头茶法，为链表添加新节点
	public void addAtHeader(T element){
//		创建新节点，让新节点的next指向原来的header，并以新节点作为新的header
		header = new Node(element,null,header);
//		如果插入之前是空链表
		if (tail == null){
			tail=header;

		}
		size++;

	}
//	删除链式线性表指定索引处的元素
	public T delete(int index){
		if(index<0 || index>size-1){
			throw new IndexOutOfBoundsException("自定义双向线型表，索引值越界");
		}
		Node del = null;
//		如果被删除的是header节点
		if (index == 0){
			del = header;
			header = header.next;
//			释放新的header节点的prev引用
			header.prev = null;
		}
		else {
//			获取删除点的前一个节点
			Node prev = getNodeByIndex(index-1);
//			获取将要被删除的节点
			del = prev.next;
//			让被删除节点的next指向被删除节点的下一个节点
			prev.next = del.next;
//			让被删除节点的下一个节点的prev指向prev节点
			if (del.next !=null){
				del.next.prev = prev;
			}
//			将被删除节点的prev，next引用赋值为null
			del.prev= null;
			del.next= null;
		}
		size--;
		return del.data;
	}
//	删除链式线性表中最后一个元素
	public T remove(){
		return delete(size-1);
	}
//	判断链式表线性表是否为空链表
	public boolean empty(){
		return size ==0;

	}
//	清空线性表
	public void clear(){
//		将底层数组所有元素赋值为null
		header = null;
		tail = null;
		size = 0;

	}

	@Override
	public String toString() {
//		return super.toString();
//		链表是否为空链表
		if (empty()){
			return "[]";
		}
		else {
			StringBuilder sb=new StringBuilder("[");
			for (Node current=header;current!=null;current=current.next){
				sb.append(current.data.toString()+",");
			}
			int len =sb.length();
			return sb.delete(len-2,len).append("]").toString();
		}

	}
	public String resverToString(){
//		链表为空
		if (empty()){
			return "[]";
		}
		else {
			StringBuilder sb=new StringBuilder("[");
			for (Node current=tail;current !=null;current=current.prev){
				sb.append(current.data.toString()+",");
			}
			int len = sb.length();
			return sb.delete(len-2,len).append("]").toString();
		}
	}
}
